The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In recent years, use of large-scale networks that exchange, process, and store large amounts of data at high speed is proliferating. Consequently, demand for reliable data storage systems is increasing. Data may be stored reliably by configuring multiple disk drives in an arrangement called a redundant array of independent disks (RAID).
RAID is a way of storing same data in different locations (i.e., redundantly) on multiple disks. Multiple disks increase mean time between failures (MTBF). Storing data redundantly increases fault tolerance. In some implementations, a RAID system may use a parity disk that stores parity information. The parity disk is updated whenever new data is written on a disk in the RAID system.
Referring now to FIG. 1, a RAID system 10 comprises a disk array 12, a RAID controller 14, and a host computer 16. The disk array 12 may comprise multiple data disks. The data disks may include Disk 1 13-1, Disk 2 13-2, . . . , Disk N 13-N (collectively data disks 13), and a parity disk 15. The RAID controller 14 may link to the host computer 16 via an interface such as small computer system interface (SCSI).
The RAID controller 14 performs read/write operations on one or more data disks 13 according to commands received from the host computer 16. Specifically, the RAID controller 14 writes data generated by the host computer 16 on one or more data disks 13. The RAID controller 14 reads data stored in one or more data disks 13 when the host computer 16 issues read commands for the data.
When new data is written on a data disk 13 in the RAID array 12, the RAID controller 14 updates the parity disk 15. Specifically, the RAID controller 14 reads data stored in the parity disk 15 and calculates an exclusive OR (i.e., an XOR, denoted by the symbol ED) of that data and the new data that is to be written on the data disk 13. The RAID controller 14 uses the result of the XOR operation to overwrite the data stored in the parity disk 15. Thus, if a data disk 13 in the RAID array 12 fails, data stored in the failed data disk 13 can be recovered by calculating XOR of the data stored on the parity disk 15 and data stored in the remaining data disks 13.
For example, suppose data A1=0000 0111 is stored on Disk 1, data A2=0000 0101 is stored on Disk 2, and data A3=0000 0000 is stored on Disk 3. In that case, parity information Ap=A1⊕A2⊕A3=0000 0010 is stored on the parity disk. If Disk 2 fails, missing data A2 can be reconstructed using the XOR operation A1⊕A3⊕Ap=A2.
Data is typically read from disks in sectors or data blocks. Data read from a disk is considered reliable if that data is the same as the data written on the disk. To enable error detection when data is read from a disk, a cyclic redundancy check (CRC) is performed on the data before the data is written on the disk. CRC for a data block is generated as follows. Data in the data block is divided by a predetermined binary keyword. A remainder resulting from the division is called a checkword or a checksum of the data in the data block. The checksum is appended to the data block before the data block is written and stored in the disk.
When the data block is read from the disk, the same division is performed, and the remainder of the division is compared to the checksum in the data block. The data in the data block is considered reliable if the remainder matches the checksum. CRC, however, may not detect errors when data read differs from data written due to an error and yet generates identical remainders in read and write operations.
An error-correcting code (ECC) enables not only detection but also correction of some errors that may be detected in a data block when the data block is read from a disk. Typically, an error-correcting code such as Reed-Solomon code is used to calculate a codeword for the data block. The codeword is calculated and appended to the data block before the data block is written and stored in the disk.
When the data block is read from the disk, the same calculation is performed, and the resulting codeword is compared to the codeword in the data block. The data in the data block is considered error-free if the two codewords match. If an error is detected, the error can be corrected. That is, correct data can be reconstructed using the codeword. Number of errors that can be corrected depends on an error-correcting capability of the code used.
In addition to the data in the data block, the parity disk stores a logical block address (LBA) of the data block. The LBA indicates an address or a location of the data block on a disk. Typically, CRC of each data block is seeded with the LBA of that data block. That is, the CRC includes the LBA information, which is also called the seed information. When the data block to be written at a LBA on a disk is XOR'ed with the data block read from the parity disk having the same LBA, the XORs of the CRCs of the two data blocks does not equal the CRC of the XOR'ed data block.
Consequently, CRC with seed information is generally regenerated for the XOR'ed data block. If CRC for the XOR'ed data block is computed using the data in the XOR'ed data block, any errors that may occur during the XOR operation and CRC regeneration may propagate undetected. Propagation of undetected errors may render the data unreliable. U.S. patent application Ser. No. 11/056,320 filed on Feb. 11, 2005, which is incorporated herein by reference in its entirety, discloses a method for regenerating CRC for the XOR'ed data block.